Có thuyết nói Nguyễn Du viết Truyện Kiều sau khi đi sứ Trung Quốc (1814–1820). Lại có thuyết nói ông viết trước khi đi sứ, có thể vào khoảng cuối Lê đầu Tây Sơn.[2] Thuyết sau được nhiều người chấp nhận hơn.[3] Ngay sau khi ra đời, Truyện Kiều được nhiều nơi khắc in và lưu hành rộng rãi. Hai bản in xưa nhất hiện còn là bản của Liễu Văn Đường (1871) và bản của Duy Minh Thị (1872), đều ở thời vua Tự Đức.[3]

Truyện dựa theo bộ truyện văn xuôi Kim Vân Kiều truyện của Thanh Tâm Tài Nhân, lấy bối cảnh Trung Quốc thời vua Gia Tĩnh Đế đời nhà Minh (từ năm 1521 tới năm 1567). Có một số nhân vật như tổng đốc Hồ Tôn Hiến, kỹ nữ Vương Thúy Kiều, nhân vật Từ Hải là có thật trong lịch sử.

Bản in khắc đầu tiên năm 1920 có tựa chính thức là Đoạn trường tân thanh (chữ Hán: 斷腸新聲), có nghĩa là "tiếng kêu mới về nỗi đau lòng đứt ruột".